1. Field of the Invention
This invention relates to the field of countermeasures against attacks on computer systems, and more particularly to a rigorous analysis method and computer software tool designed to identify which parts of a computer network are most vulnerable to attack by an adversary. Specifically, according to the invention, an attack graph is generated based on hypothesized capabilities of an adversary, network configuration information, and knowledge of the requirements for a successful attack. An attack graph generated in this fashion is then analyzed to determine high-risk attack paths and to provide insight into how to reduce network vulnerability.
2. Description of the Related Art
Military, government, commercial, and civilian operations all depend upon the security and availability of computer systems and networks. Over the past decade, people have become more aware of the need for information security as intrusions, attacks, and viruses have become more frequent and widespread. According to the Commission Report of the Presidential Commission of Critical Infrastructure Protection, “Critical Foundations: Protecting America's Infrastructures” (October 1997), industry and government are vulnerable to attack through their reliance on information technologies. Academia and computer companies have responded to the security problem by developing hardware (e.g. firewalls) and software (e.g. scanning tools) to identify threats and vulnerabilities and protect information assets. The current approach to information assurance, however, is often driven by checklists and compliance standards, and not by an overall understanding of system requirements and the components chosen to implement those requirements within a required risk level. Further, current methods do not trace causality throughout a system.
Quantifying security risks in computer networks is very difficult. Ideally, a network-vulnerability risk-analysis system should be able to model the dynamic aspects of the network (e.g., virtual topology changing), multiple levels of attacker ability, multiple simultaneous events or multiple attacks, user access controls, and time-dependent, ordered sequences of attacks. A tool that quantitatively identifies vulnerable paths and nodes in a networked environment would be useful both in the design and assessment of information systems.
In assessing the problem of network vulnerabilities various approaches have been tried in the past. Probabilistic Risk Assessment (PRA) techniques such as fault-tree and event-tree analysis provide systematic methods for examining how individual faults can either propagate into or be exploited to cause unwanted effects on systems. These methods, however; have limited effectiveness in the analysis of computer networks because they cannot model multiple attacker attempts, time dependencies, or access controls. In addition, fault trees don't model cycles (such as an attacker starting at one machine, hopping to two others, returning to the original host, and starting in another direction at a higher privilege level). Methods such as influence diagrams and event trees suffer from the same limitations as fault trees.
Computer security/risk analysis tools have been developed that perform the function of scanning to check for the presence of previously identified services or conditions known to result in network vulnerability. Such tools, however, do not consider the physical network topology in conjunction with set of attacks. A seminal tool, SATAN (Security Administrator Tool for Analyzing Networks) created by D. Farmer and W. Venema. Lawrence Livermore National Laboratory maintains an Internet site on the World Wide Web (http://ciac.llnl.gov/ciac/ToolsUnixNetSec.html#Satan) from which, at the time the present application for patent is made, information can be obtained regarding this tool. SATAN checks a “laundry list” of services or conditions that are enabled on a particular machine. For example, on UNIX systems SATAN checks for NFS file systems exported to unprivileged programs or arbitrary hosts, but gives little indication of how these items lead to system compromise. More recent scanners such as the Internet Scanner™ from Internet Security Systems, Inc. (ISS) probe the network and provide information about potential vulnerabilities that could be exploited. (ISS is located at 41 Perimeter Center East, Suite 550, Atlanta, Ga. 30346, and as of the time this application is being prepared, information about Internet Scanner™ is available via the Internet at http://www.iss.net/xforce). These scanning tools can provide a system administrator with a set of items to patch or fix. However, these scanners do not verify that all conditions for a complete attack are met, nor do they identify linked attacks potentially more harmful than individual attacks. Though they can suggest fixes for local potential problems, they don't consider the network as a whole, proposing a global set of cost-effective defenses designed to protect the network's most critical resources.
Using a different approach, Dacier, et al. propose using a “privilege graph” to represent complex attacks with a single edge. (Dacier, M., Y. Deswarte, and M. Kaaniche. “Quantitative Assessment of Operational Security: Models and Tools.” LAAS Research Report 96493, May 1996). Although Dacier, et al. use a graph to assist in network vulnerability analysis, the function of the graph is distinguishable from the attack graphs of the present invention to be described below. The privilege graph does not explicitly represent attacker capabilities and is based mainly on the acquisition of “privileges” of the user (e.g., the ability to read, write, and modify certain files). On the other hand, the attack graph of the present invention encapsulates a much richer definition of “state” of a node including changes made by the attacker to the configuration, capabilities acquired by the attacker at various stages of an attack and other factors. Dacier, et al. transform the privilege graph into a Markov model and determine the estimated mean time and effort to target by enumerating all searches in the privilege graph. The Markov model represents all possible probing sequences of a non-omniscient attacker. Ortalo et al. present experimental results using this model, based on a privilege graph constructed from 13 major UNIX vulnerabilities. They conclude that Mean Effort to Failure (METF) is more valuable as a security metric than the single shortest path or raw number of paths to target. However, they were not always able to compute METF, even for fairly small graphs. (See: “Experimenting with Quantitative Evaluation Tools for Monitoring Operational Security,” by R. Ortalo, Y. Deswarte, and M. Kaaniche in IEEE Transactions on Software Engineering, Vol. 25, No. 5, September/October 1999).
It is against this background that the present invention was made. A need exists for a system that does identify high-risk attack paths and linked sequences of attack steps in an attack graph. There also remains a need for a system that is user friendly and has an instructive interface that identifies critical paths.